package com.fr.lintcode.dp;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月23日
*时间：下午3:14:50
*/
public class package01 {
    /**
     * 物品重量  物品价值
     * 3    4
     * 4    5
     * 5    6
     * 背包承重M =10, 物品个数N=3
     * */
    int c[][];
    int w[] = { 3, 4, 5 };
    int p[] = { 4, 5, 6 };

    @Test
    public void TestA() {
        int m = 10;
        int n = p.length;
        c = new int[n + 1][m + 1];
        packageTest(n, m);
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                System.out.print(c[i][j] + "\t");
            }
            System.out.println();
        }
    }

    private void packageTest(int n, int m) {
        for (int j = 0; j < m + 1; j++) {
            for (int i = 0; i < n + 1; i++) {
                if (i == 0 || j == 0) {
                    c[i][j] = 0;
                } else if (j < w[i - 1]) {
                    c[i][j] = c[i - 1][j];
                } else if (c[i - 1][j - w[i - 1]] + p[i - 1] > c[i - 1][j]) {
                    c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
                } else {
                    c[i][j] = c[i - 1][j];
                }
            }
        }
    }
}
